[SP15637][POJ2279]GNYR04H - Mr Youngs Picture Permutations

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

杨先生希望为他的班级拍照。学生将排成一行，每行不超过后面的行，并且行的左端对齐。例如，可以安排12名学生排列（从后到前）5,3,3和1名学生。

1
2
3
4
X X X X X
X X X
X X X
X

此外，杨先生希望每排学生安排高度从左到右减少。此外，学生身高应从后向前减少。想想看，杨先生看到，对于这个12人的例子，至少有两种安排学生的方式（数字代表高度，其中1代表最高）：

1
2
3
4
1  2  3  4  5     1  5  8 11 12
6  7  8           2  6  9
9 10 11           3  7 10
12                4

杨先生想知道，对于给定排列的排列，可能有多少不同的学生安排。他尝试用长度为3,2和1的行开始计数，并计数16个排列：

1
2
3
123 123 124 124 125 125 126 126 134 134 135 135 136 136 145 146
45  46  35  36  34  36  34  35  25  26  24  26  24  25  26  25
6   5   6   5   6   4   5   4   6   5   6   4   5   4   3   3

杨先生认为，手动点数对于任何合理数量的学生来说都不会很有效。他通过编写计算机程序来帮助你确定一组给定行的学生的不同安排数量。

输入格式

输入描述了一系列测试，每个测试分两行描述。第一行将行数k作为十进制整数。第二行包含从后到前的行的长度（n {1} 1 ，n {2} 2 ，…，n _ {K} ķ ）作为由单个空格分隔的十进制整数。问题集以行计数为0的行结束。最多不会超过5行，学生总数N（行长度总和）最多不超过30行。

输出格式

对于每个测试用例输出一个整数：N个学生排列在给定行中的数量，以便高度从左到右沿着每行减少，并且从后到前沿着每列减小（假定所有高度都不同）。结果应该分开。输入数据将被选择，以便结果总是适合一个无符号的32位整数。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
1
30
5
1 1 1 1 1
3
3 2 1
4
5 3 3 1
5
6 5 4 3 2
2
15 15
0

输出样例

1
2
3
4
5
6
1
1
16
4158
141892608
9694845

翻译by@_UMR_

题解

看到网上很多人说《算法竞赛进阶指南》上的方法不行，会MLE
那动态开空间不就是了……
在合法的方案中，每一行，每一列都是单调的，也就是说我们要确保每一次放的时候，放的人要小于左边的，上面的。
其实这也很好办，假设我们放的人的高度是递减的，第一行我们只要放得去，就能满足单调，而下面几行，只要各自人数小于等于上面一行的人数就OK了。
让我们来看看这一题的“动态规划信息表”

信息 表示方式 解释
状态 $F_{a_1,a_2,a_3,a_4,a_5}$ 表示各排从左端起，分别占了$a_1,a_2,a_3,a_4,a_5$个人时，合影方案数量
边界 $F_{0,0,0,0,0}=1$ 其余为0
目标 $F_{N_1,N_2,N_3,N_4,N_5}$ 无
转移 无 若$a_1<N_1$,则令$F_{a_1+1,a_2,a_3,a_4,a_5}+=F_{a_1,a_2,a_3,a_4,a_5}$。若$a_2<N_2\&\&a_1>a_2$则令$F_{a_1,a_2+1,a_3,a_4,a_5}+=F_{a_1,a_2,a_3,a_4,a_5}$ 第3~5同理

至于杨氏矩阵和钩长公式，还请大家自行了解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<cstdio>
#include<cstring>
using namespace std;
int k,a[6],n[6];

int main(){
    while(scanf("%d",&k)){
    	if(k==0)break;
        memset(n,0,sizeof(n));
        for(int i=1;i<=k;i++) scanf("%d",&n[i]);
        int f[n[1]+1][n[2]+1][n[3]+1][n[4]+1][n[5]+1];
        memset(f,0,sizeof(f));
        f[0][0][0][0][0]=1;
        for(a[1]=0;a[1]<=n[1];a[1]++)
        	for(a[2]=0;a[2]<=n[2];a[2]++)
          		for(a[3]=0;a[3]<=n[3];a[3]++)
           			for(a[4]=0;a[4]<=n[4];a[4]++)
            			for(a[5]=0;a[5]<=n[5];a[5]++){
            				int t=f[a[1]][a[2]][a[3]][a[4]][a[5]];
                            if(a[1]<n[1]) f[a[1]+1][a[2]][a[3]][a[4]][a[5]]+=t;
                            if(a[2]<n[2]&&a[1]>a[2]) f[a[1]][a[2]+1][a[3]][a[4]][a[5]]+=t;
                            if(a[3]<n[3]&&a[2]>a[3]) f[a[1]][a[2]][a[3]+1][a[4]][a[5]]+=t;
                            if(a[4]<n[4]&&a[3]>a[4]) f[a[1]][a[2]][a[3]][a[4]+1][a[5]]+=t;
                            if(a[5]<n[5]&&a[4]>a[5]) f[a[1]][a[2]][a[3]][a[4]][a[5]+1]+=t;
        				}
        printf("%d\n",f[n[1]][n[2]][n[3]][n[4]][n[5]]);
    }
    return 0;
}